#include<iostream>
#include<vector>
#include<string>
using namespace std;
#define MAX 10
//n皇后问题

vector<vector<string>> result;
//存放列，正对角线（左上到右下），对角线2是否能放皇后
bool column[MAX],daig1[MAX*2],daig2[MAX*2];
vector<string> temp;
//r为行数
void dfs(int r,int n)
{
    //若行数等于n则将该结果存入结果集
    if(r==n)
    {         
        result.push_back(temp);
        return;
    }
    else
    {
        //递归存储列
        for(int i=0;i<n;i++)
        {
            //对角线与行列的关系为正对角线行列之差相同，反对角线行列之和相同
            if(!column[i]&&!daig1[r+i]&&!daig2[r-i+n])
            {
                temp[r][i]= 'Q';
                column[i]=daig1[r+i]=daig2[r-i+n]=true;
                dfs(r+1,n);
                //回溯，回复状态，进行下一列查找
                temp[r][i]= '.';
                column[i]=daig1[r+i]=daig2[r-i+n]=false;
            }
        }
    }
}
vector<vector<string>> solveNQueens(int n) {
    temp.resize(n,string(n,'.'));
    //先放第一行皇后
    dfs(0,n);
    return result;
}
int main()
{
    cout<<"enter the numbers of kings:"<<endl;
    int n;
    cin >> n;
    vector<vector<string>> ans = solveNQueens(n);
    for(auto i:ans){
        for(auto j:i){
            cout<<j<<" ";
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}